In the development of fifth generation computers, computer vision is one of the major topics. Computer vision consists of two parts, i.e. image processing and pattern recognition. Having been processed, a pattern shows its individual characteristic for recognizing. For example, feature points of a finger print are obtained with the processing operation and the feature points are used to check if the finger print is a particular one.
In computer reading or scanning of language characters, it is also possible to recognize the characters with the point pattern matching technique. FIG. 1-1 shows a hand-writing of a Chinese character. After being processed, the feature points obtained by a computer are shown in FIG. 1-2. FIG. 2-1 shows a different hand-writing of the same Chinese character and the feature points obtained therefrom are shown in FIG. 2-2. The computer recognizes one of the characters, e.g. that of FIG. 1-1, by comparing the point pattern of FIG. 1-2 to that of FIG. 2-2 to decide if they are the feature point patterns obtained from the identical Chinese characters of FIG. 2-1.
For those who understand Chinese, FIGS. 1-1 and 2-1 represent the same character. However, a computer can only decide this through a special procedure of comparison to be described.
Generally speaking, the comparison procedure comprises two kinds of operations matching and registration.
The matching procedure is finding a one-to-one correspondence between points of a first planar point pattern and those of a second planar point pattern. That is, a point of the first planar point pattern has one and only one point of the second planar point pattern is associated therewith.
The registration procedure is to translate, rotate and/or scale the first planar point pattern in a Euclidean plane so as to obtain an even similar pattern to the second planar point pattern (reference planar point pattern), and to more precisely determine the similarity therebetween.
In image processing and pattern recognition for, such as, written characters and finger prints, there are two major difficulties, (1) the difference of the Number of feature points between two planar point patterns and (2) the unpredictable probability of a feature point appearing in both patterns, for example, the feature points of FIG. 2-2 should have a same number in theory but they do not. It is quite different between the zones marked p.sub.1 and q.sub.1 and those marked p.sub.2 and q.sub.2 in the figures. Not only are the point numbers different, but also the distributions thereof are different and difficult to predict.
Finger prints are another example. A finger print is a unique identification of a person that never changes for the whole life of a person. To recognize finger prints by use of the computer image processing technique in order to decide if two finger prints are a particular one is a goal that has been aimed at for a long time by the scientists. Since the tips of the fingers are soft and flexible, the finger prints thereof are usually distorted when the finger tips are pressed against a glass surface. Therefore, it is not possible for the feature points to completely show on the pattern to be processed. Statistically, the probability of the feature points of a finger print repeating in two patterns is only 60%.
Besides, the pressure exerted by distribution of the finger tip also affects the distribution of the feature points. The direction of the pressure usually rotates or translates the pattern. This increases the difficulty in comparing patterns finger prints.